#include<bits/stdc++.h>
#define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,base=999983,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int n,m;
set<int>s[N],rs[N],q[N],rq[N];
int dp[N],in[N];
int col[N];
int gg[N],tot;
int ans=0;
void dfs(int x){
	if(x==n){
		For(i,0,n-1) q[i].clear(),rq[i].clear();
		For(i,0,n-1){
			for(auto v:s[i]) q[col[i]].insert(col[v]);
			for(auto v:rs[i]) rq[col[i]].insert(col[v]);
		}tot=0;
		For(i,0,n-1){
			if(q[i].size()||rq[i].size()){
				gg[tot++]=i;
			}
		}
		For(i,0,tot-1){
			if(q[gg[i]].find(gg[(i+1)%tot])==q[gg[i]].end()){
				return;
			}
			For(j,0,tot-1){
				if(j!=(i+1)%tot){
					if(q[gg[i]].find(gg[j])!=q[gg[i]].end()){
						return;
					}
					
				}
			}
		}
//		For(i,0,n-1) cout<<col[i]<<" ";puts("");
//		For(i,0,tot-1) cout<<gg[i]<<" ";puts("");
//		For(i,0,tot-1){
//			for(auto v:q[i]) printf("%lld",v);
//			puts("");
//		}
//		puts("_______");
		ans=max(ans,tot);
		return;
	}
	For(i,0,n-1){
		col[x]=i;
		dfs(x+1);
		col[x]=0;
	}
}
int dep[N];
signed main(){
	freopen("circ.in","r",stdin);
	freopen("circ.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	int T=read();
	while(T--){
		n=read(),m=read();
		For(i,1,m){
			int u=read(),v=read();
			s[u].insert(v);
			rs[v].insert(u);
			in[v]++;
		}ans=0;
		if(n<=7){
			dfs(0);
			printf("%lld\n",n-ans);
		}
		else{
			queue<int>q;
			For(i,0,n-1) if(in[i]==0){
				q.push(i);dep[i]=1;
			} 
			while(!q.empty()){
				int x=q.front();q.pop();
				for(auto v:s[x]){
					in[v]--;dep[v]=max(dep[v],dep[x]+1);
					ans=max(ans,dep[v]);
					if(in[v]==0) q.push(v);
				}
			}printf("%lld\n",n-ans);
		}
//		puts("____________________________");
		For(i,0,n) s[i].clear(),rs[i].clear(),in[i]=0;
	}
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

